#include <stdlib.h>
#include <string.h>

#include <tvm/tvm_htab.h>

#define HTAB_LOAD_FACTOR 0.7 // 阈值

// 创建hash table
struct tvm_htab_ctx  *tvm_htab_create()
{
    struct tvm_htab_ctx *htab = (struct tvm_htab_ctx *)calloc(1, sizeof(struct tvm_htab_ctx));

    htab->size = HTAB_SIZE;
    htab->nodes = (struct tvm_htab_node **)calloc(htab->size, sizeof(struct tvm_htab_node *));
    htab->num_nodes = 0;
	return htab;
}

void tvm_htab_destroy(struct tvm_htab_ctx *htab)
{
	struct tvm_htab_node *node, *next;

	for (int i = 0; i < htab->size; i++) {
		node = htab->nodes[i];
		while (node) {
			next = node->next;
			if (node->valptr)
				free(node->valptr);
			free(node->key);
			free(node);
			node = next;
		}
	}

	free(htab->nodes);
	free(htab);
}

static inline unsigned int htab_hash(const char *k, const unsigned int size)
{
	unsigned int hash = 1;

    char *c;
    for (c = (char *)k; *c; c++)
        hash += (hash << *c) - *c;

	return hash % size;
}

// 根据传入的size重新计算hash table
static void htab_rehash(struct tvm_htab_ctx  *orig, unsigned int size)
{
	int i;
	struct tvm_htab_node *node, *next;
	struct tvm_htab_ctx  *new;

	new = (struct tvm_htab_ctx  *)calloc(1, sizeof(struct tvm_htab_ctx));
    new->nodes = (struct tvm_htab_node **)calloc(size, sizeof(struct tvm_htab_node *));
    new->size = size;
	new->num_nodes = 0;

	/* Traverse the original hash table, rehashing
	 * every entry into the new table and deleting
	 * original entries
	 */
    // 遍历原始哈希表
    for (i = 0; i < orig->size; i++) {
		node = orig->nodes[i];
		while (node) {
			next = node->next;
			if (node->valptr) { // 如果该指针不为空
				tvm_htab_add_ref( // 将旧的指针内容拷贝到新指针对应地址上
					new, node->key,
					node->valptr,
					strlen(node->valptr) + 1
				);

                free(node->valptr); // 释放旧的内存
            } else { // 为空则新建
                tvm_htab_add(new, node->key, node->value);
            }

			free(node->key); // 释放旧的table key
			free(node); // 释放旧的table node
			node = next; // 当前节点切换到下一个
		}
	}

	free(orig->nodes); // 释放原始hash table的所有节点地址空间

	/* Transpose the new hash table onto the old one */
    // 将new的所有内容拷贝到orig上
	memcpy(orig, new, sizeof(struct tvm_htab_ctx));
	free(new); // 释放new申请的空间
}

static struct tvm_htab_node *htab_add_core(struct tvm_htab_ctx *htab, const char *k)
{
	/* Increase bucket count and rehash if the
	 * load factor is too high
	 */

    // 当当前空间占用率达到了70%，就需要重新排列hash表
    // 重新排列方法为将hash表扩大到当前2倍
	if ((float) ++htab->num_nodes / htab->size > HTAB_LOAD_FACTOR)
		htab_rehash(htab, htab->num_nodes * 2);

    // 获取一个空闲的节点
    int hash = htab_hash(k, htab->size);                // 根据k算出hash值，实际是一个int类型的值，该值作为数组的索引
    struct tvm_htab_node *node = htab->nodes[hash];     // 根据索引获取指针
    struct tvm_htab_node *prev = NULL;                  // 申明

    if (node) {                                         // 找到最后一个空节点
        while (node->next)                              // 如果当前节点的下一个不为NULL（空指针）
            node = node->next;                          // 接着找下一个指针，直到找到一个空指针

        prev = node;                                    // 将找到的这个空节点赋值给prev
	}

	/* Allocate space, and copy the key/value pair. */

    node = calloc(1, sizeof(struct tvm_htab_node));     // 根据结构体大小申请堆内存

    node->key = (char *)calloc((strlen(k) + 1), sizeof(char)); // 给这个节点的key字段申请空间
    strcpy(node->key, k);                               // 将key的内容复制到新申请的空间里

    if (prev)                                           // 将新增节点挂在到最后一个空节点上
		prev->next = node;
	else
        htab->nodes[hash] = node;	/* root node */     // 如果prev为空指针，说明没找到空余空间，则将节点挂载到以hash值为索引的数组元素中

    node->next = NULL;                                  // 设置当前节点的下一个节点值为空

    return node;                                        // 返回当前节点
}

int tvm_htab_add(struct tvm_htab_ctx *htab, const char *key, int value)
{
	struct tvm_htab_node *node = htab_add_core(htab, key);

	if (!node)
		return -1;

	node->value = value;

	return 0;
}

int tvm_htab_add_ref(struct tvm_htab_ctx *htab, const char *key, const void *valptr, int len)
{
	struct tvm_htab_node *node = htab_add_core(htab, key);

	if (!node)
		return -1;

	node->valptr = calloc(len, sizeof(char));
	memcpy(node->valptr, valptr, len);

	return 0;
}

static struct tvm_htab_node *htab_find_core(struct tvm_htab_ctx *htab, const char *key)
{
	int hash = htab_hash(key, htab->size);
	struct tvm_htab_node *node = htab->nodes[hash];

	while (node) {
		if (!strcmp(node->key, key))
			return node;

		node = node->next;
	}

	return NULL;
}

int tvm_htab_find(struct tvm_htab_ctx  *htab, const char *key)
{
	struct tvm_htab_node *node = htab_find_core(htab, key);

	if (!node)
		return -1;

	return node->value;
}

char *tvm_htab_find_ref(struct tvm_htab_ctx  *htab, const char *key)
{
	struct tvm_htab_node *node = htab_find_core(htab, key);

	if (!node)
		return NULL;

	return node->valptr;
}
